<?php

class TrieTree{ 
   
    public $tree = array(); 
   
    public function insert($utf8_str){ //插入敏感词
	// $chars = &UTF8Util::get_chars($utf8_str); 
      //  $chars = UTF8Util::get_chars($utf8_str); 
	  // $chars=pg_escape_string($utf8_str); 
	  $chars=array();
	  //echo $array["陈"]="陈";
		$l= mb_strlen($utf8_str,"UTF-8");
		for($i=0;$i<$l;$i++){
			if($i==$l-1)
				{	
					$chars[mb_substr($utf8_str,$i,1,"UTF-8")]= 0;//字符串结尾
					$chars["null"]=0;
				}
			else
				 $chars[mb_substr($utf8_str,$i,1,"UTF-8")]= 1;
		}
		
       // $chars[] = null;    //串结尾字符 
       // $count = count($chars); 
        $T = &$this->tree; 
		foreach($chars as $key=>$value){
		
			if(!array_key_exists($key, $T)){ 
                $T[$key] = array();   //插入新字符，关联数组 
				//echo $key."<br/>";
				
				
            }
			 $T = &$T[$key]; 
				//echo $value.'<br>';
		}
     
    } 
   
    public function remove($utf8_str){ //删去敏感词
        $chars = &UTF8Util::get_chars($utf8_str); 
        $chars[] = null; 
        if($this->_find($chars)){    //先保证此串在树中 
            $chars[] = null; 
            $count = count($chars); 
            $T = &$this->tree; 
            for($i = 0;$i < $count;$i++){ 
                $c = $chars[$i]; 
                if(count($T[$c]) == 1){     //表明仅有此串 
                    unset($T[$c]); 
                    return; 
                } 
                $T = &$T[$c]; 
            } 
        } 
    } 
   
    private function _find(&$chars){ 
        $count = count($chars); 
        $T = &$this->tree; 
        for($i = 0;$i < $count;$i++){ 
            $c = $chars[$i]; 
            if(!array_key_exists($c, $T)){ 
                return false; 
            } 
            $T = &$T[$c]; 
        } 
        return true; 
    } 
   
    public function find($utf8_str){ 
        $chars = &UTF8Util::get_chars($utf8_str); 
        $chars[] = null; 
        return $this->_find($chars); 
    } 
   
    public function contain($utf8_str, $do_count = 0){ //$do_count  表示是否统计敏感词数
        // $chars = UTF8Util::get_chars($utf8_str); 
        //$chars[] = null; 
       // $len = count($chars); 
       $Tree = &$this->tree; 
        $count = 0; 
	   $chars=array();
	  //echo $array["陈"]="陈";
		 $l= mb_strlen($utf8_str,"UTF-8");
		 $j=1;
		for($i=0;$i<$l;$i++){
		//echo mb_substr($utf8_str,$i,1,"UTF-8")."<br/>";
		$key=mb_substr($utf8_str,$i,1,"UTF-8");
			if($i==$l-1)
				$chars[mb_substr($utf8_str,$i,1,"UTF-8")]= 0;//字符串结尾
			else
				$chars[mb_substr($utf8_str,$i,1,"UTF-8")]= 1;
		
		//////////////////////
		
				//foreach($chars as $key=>$value){
					//echo $key."cccaaddddddddddddddddddddddddddaaaaaaaaa<br/>";
					
					if(array_key_exists($key, $Tree)){ //起始字符匹配 
					   // $T[$c] = array();  
					  // echo $key."vvvv<br/>";
						$T = &$Tree[$key];  
						//$new=array();
						//$new=array_slice($chars,$j);
						$new=mb_substr($utf8_str,$i+1,$l-$i,"UTF-8");
						//reset($new); 
						//foreach($new as $keynext=>$valuenext){
						for($k=0;$k<$l-$i;$k++){
							$keynext=mb_substr($new,$k,1,"UTF-8");
							//echo $keynext."eeeeeeeee<br/>";
							if(array_key_exists("null", $T)){
							//echo "nullqwwww";
								if($do_count){ 
								//echo "++1<br/>";
									//$count++; 
								} 
								else{ 
									return true; 
								}
							}
							if(!array_key_exists($keynext, $T)){ 
								break; 
							} 
							// echo $keynext."cccc<br/>";
							$T = &$T[$keynext]; 
							if(array_key_exists("null", $T)){
							//echo "nullqwwww";
								if($do_count){ 
								//echo "hou++1<br/>";
								    $count++; 
								} 
								else{ 
									return true; 
								}
							}
						}// }//forech
						 // reset($new);
						 //unset($new); 
						
						
					}
					 $j=$j+1;
					 //$T = &$T[$key]; 
					reset($Tree); 
						//echo $value.'<br>';
				//}//foreach
		}//for
        if($do_count){ 
		//echo "aaa";
            return $count; 
        } 
        else{ 
            return false; 
        } 
    } 
   
    public function contain_all($str_array){ 
		
        foreach($str_array as $str){ 
            if($this->contain($str)){ 
                return true; 
            } 
        } 
        return false; 
    } 
   
    public function export(){ 
        return serialize($this->tree); 
    } 
   
    public function import($str){ 
        $this->tree = unserialize($str); 
    } 
   
} 


?>
